#include <iostream>
#include <vector>
#include <queue>

using namespace std;
// 207.课程表
// 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，
// 表示如果要学习课程 ai 则 必须 先学习课程  bi 。
//请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        to = vector<vector<int>>(numCourses, vector<int>());
        inDeg = vector<int>(numCourses, 0); // 不能忘记初始化，否则会报错
        // 建图：出边数组
        for(vector<int>& pre : prerequisites) {
            int ai = pre[0];
            int bi = pre[1];
            to[bi].push_back(ai);   // bi-->ai
            inDeg[ai]++;
        }
        queue<int> q;
        // 拓扑排序第一步：从零入度点出发
        for(int i = 0; i < numCourses; i++)
            if(inDeg[i] == 0) q.push(i);
        vector<int> lessons;    // 修的课程
        while(!q.empty()) {
            int x = q.front();
            q.pop();
            lessons.push_back(x);
            // 第二步：扩展一个点，周围的点入度点减一
            for(int y : to[x]) {
                inDeg[y]--;
                // 第三步：入度减为0，表示可以入队了
                if(inDeg[y] == 0) {
                    q.push(y);
                }
            }
        }
        return lessons.size() == numCourses;
    }

private:
    vector<vector<int>> to; // 出边数组
    vector<int> inDeg;  // 入度
};


int main() {
    std::cout << "Hello, World!" << std::endl;
    return 0;
}
